package com.tgy.algorithm.base._二叉树;


class BSFInfo {
    boolean isBSF;
    int maxNum;
    int minNum;
    int maxBSFNum;
    BSFInfo(boolean isBSF,int maxNum,int minNum,int maxBSFNum) {

        this.isBSF = isBSF;
        this.maxNum = maxNum;
        this.minNum = minNum;
        this.maxBSFNum = maxBSFNum;
    }
}

public class _查找二叉树中最大搜索二叉树的节点数 {

    public static BiTreeNode generalBiTreeNode() {
        /**
         *              9
         *         6           11
         *      4     8     10
         *
         */
        BiTreeNode root = new BiTreeNode(9);
        root.left = new BiTreeNode(6);
        root.right = new BiTreeNode(11);
        root.left.left = new BiTreeNode(4);
        root.left.right = new BiTreeNode(8);
        root.right.left = new BiTreeNode(10);
        return root;
    }

    public static int getMaxBSFNodeNum(BiTreeNode root) {

        if (root == null) {
            return 0;
        }

        return doGetMaxBSFNodeNum(root).maxBSFNum;
    }

    public static BSFInfo doGetMaxBSFNodeNum(BiTreeNode root) {

        if (root == null) {
            return null;
        }
        BSFInfo leftInfo = doGetMaxBSFNodeNum(root.left);
        BSFInfo rightInfo = doGetMaxBSFNodeNum(root.right);


        int minNum = root.val;

        if (leftInfo != null ) {
            minNum = Math.min(minNum,leftInfo.minNum);
        }

        int maxNum = root.val;
        if (rightInfo != null) {
            maxNum = Math.max(maxNum,rightInfo.maxNum);
        }


        int maxBSFNum = 0;
        // 左边的最大值，右边的最小值
        boolean isBSF = false;

        boolean leftIsBSF = (leftInfo == null || leftInfo.isBSF);
        boolean rightIsBSF = (rightInfo == null || rightInfo.isBSF);
        if (leftIsBSF && rightIsBSF) {
            isBSF = true;
            if (leftInfo != null && leftInfo.maxNum >= root.val) {
                isBSF = false;
            }

            if (rightInfo != null && rightInfo.minNum <= root.val) {
                isBSF = false;
            }
        }

        if (isBSF) {
            maxBSFNum = (leftInfo == null?0:leftInfo.maxBSFNum) + 1 + (rightInfo == null?0:rightInfo.maxBSFNum);
        }else {
            maxBSFNum = Math.max(leftInfo == null?0:leftInfo.maxBSFNum, rightInfo == null?0:rightInfo.maxBSFNum);
        }
        return new BSFInfo(isBSF, minNum, maxNum, maxBSFNum);
    }


    public static void main(String[] args) {

        BiTreeNode root = generalBiTreeNode();
        int maxBSFNodeNum = getMaxBSFNodeNum(root);
        System.out.println(maxBSFNodeNum);
    }
}
